Introduction

Often times, an ensemble of methods will perform better than the individual method. This known as the “wisdom of the crowds” phenomenon. An easy way to generate an ensemble prediction is to take the mean, median, or weighted average of all of the predictions. You then can score this “prediction” as you would any other prediction file to assess it’s performance relative to the submissions.

Another consideration is that the wisdom of the crowds method sometimes applies only to a certain point. That is, if you order all of the submitted predictions from high to low performance, there may be a point after which you no longer want to add a prediction to your ensemble method. A good visualization of this can be found in Supplemental Figure 8 here, where you can see how the ensemble score changes after adding additional predictions. Performance peaks with an ensemble of the top four predictions, but does not improve with additions of further models.

A final consideration here is that certain models may be better at predicting certain components of the problem. You may be able to more strategically ensemble methods if you assess the performance of the submitted models on categorical subsets of the data (e.g. for a method predicting among four cancer subtypes, some methods may be better at predicting subtype 1 vs the other methods, while other methods may be better at predicting subtype 3 than other methods). Weighting the predictions from these methods strategically may result in better ensemble performance.

First, import packages, scoring functions, and challenge data.

library(tidyverse)
library(reticulate)
# library(reactable)
use_condaenv("synapse-2") #conda environment with synapse >2.0 installed
synapse <- import('synapseclient')
syn <- synapse$Synapse()

Scoring helper functions.

# 
calculate_weight <- function(x){
  weight <- dplyr::if_else(x == 0, 1,
            dplyr::if_else(x == 1, 2,
            dplyr::if_else(x>=2 & x<=3, 2.143547,
            dplyr::if_else(x>=4 & x<=7, 3.863745,
            dplyr::if_else(x>=8 & x<=20, 8,
            dplyr::if_else(x>=21 & x<=55, 16,
            dplyr::if_else(x>=56 & x<=148, 32,
            dplyr::if_else(x>=148, 64, 0))))))))
  return(weight)
}

# 
sum_weighted_error <- function(gold, pred, weight){
  sum(weight*abs(gold - pred))
}

# 
rmse <- function(gold, pred){
  sqrt(mean((gold - pred) ** 2))
}

# Scoring function for joint weighted sum RMSE.
score_weighted_rmse <- function(df, pred) {
  df$pred_score <- pred
  df %>% group_by(Patient_ID, weight) %>%
    summarize(patient_rmse = rmse(log2(score+1), log2(pred_score+1))) %>% 
    ungroup() %>% 
    summarize(result= sum(weight*patient_rmse)/sum(weight)) %>%
    pluck("result")
}

Goldstandard

For the validation round, we have two expert reader measurements. Previous analysis showed that the validation predictions scored relatively concordantly between these two gold-standards, so to simplify this analysis we’ll take the average of the two datasets for each measurement.

The assessment of subchallenge 1 utilizies known SvH scores and subchallenges 2 & 3 known individual joint narrowing and erosion scores. After adding a weight for each joint score, split the goldstandard accordingly.

gold.sc1 <- gold %>% 
  select(Patient_ID, Overall_Tol, weight)
Error: Can't subset columns that don't exist.
x Column `weight` doesn't exist.
Run `rlang::last_error()` to see where the error occurred.

Bootstrap Submissions

Read in prediction files, combine, then bootstrap the predictions + a gold standard 1000 times to calculate 1000 scores per prediction.

p
[[1]]

[[2]]

[[3]]

[[4]]

[[5]]

[[6]]

[[7]]

[[8]]

[[9]]

[[10]]

[[11]]

[[12]]

[[13]]

[[14]]

p
[[1]]

[[2]]

[[3]]

[[4]]

[[5]]

[[6]]

[[7]]

[[8]]

[[9]]

[[10]]

[[11]]

[[12]]

[[13]]

[[14]]

bs_indices.sc2 <- matrix(1:nrow(ensemble.sc2), nrow(ensemble.sc2), N) %>%
  apply(2, sample, replace = T)
boot.sc2 <- apply(bs_indices.sc2, 2, function(ind) {
  tmp.gold <- ensemble.sc2[ind, c(1:4)]
  apply(ensemble.sc2[ind, -c(1:4)], 2, function(pred) {
    score_weighted_rmse(tmp.gold, pred)
  })
}) %>%
  t()
p
[[1]]

[[2]]

[[3]]

[[4]]

[[5]]

[[6]]

[[7]]

[[8]]

[[9]]

[[10]]

[[11]]

[[12]]

[[13]]

[[14]]

bs_indices.sc2 <- matrix(1:nrow(ensemble.sc2), nrow(ensemble.sc2), N) %>%
  apply(2, sample, replace = T)
boot.sc2 <- apply(bs_indices.sc2, 2, function(ind) {
  tmp.gold <- ensemble.sc2[ind, c(1:4)]
  apply(ensemble.sc2[ind, -c(1:4)], 2, function(pred) {
    score_weighted_rmse(tmp.gold, pred)
  })
}) %>%
  t()
### SC3
submissions.sc3 <- lapply(names(pred_filenames), function(team) {
  read.csv(pred_filenames[[team]]) %>% 
    select(-Overall_Tol) %>%
    gather('joint', !!team, -Patient_ID)
}) %>%
  reduce(left_join, by=c("Patient_ID", "joint")) %>%
  left_join(gold_joints, by=c("Patient_ID", "joint"))
results.sc3 <- submissions.sc3[, c(
    "Patient_ID", "joint", "weight", "score", (query %>% arrange(sc3))$submitterid
  )] %>%
  filter(grepl(".+_E__.+", joint))
ensemble.sc3 <- sapply(5:ncol(results.sc3), function(x){
  new_col <- results.sc3 %>% 
    select(5:x) %>% 
    mutate(!!sym(as.character(x)) := rowMeans(across(where(is.numeric)))) %>% 
    pluck(as.character(x))
}) %>% 
  as.data.frame()
ens_names <- c(glue::glue("{colnames(results.sc3)[5]}"), glue::glue("+{colnames(results.sc3)[-1:-5]}"))
colnames(ensemble.sc3) <- ens_names
ensemble.sc3 <- ensemble.sc3 %>% 
  add_column(weight = results.sc3$weight,
             score = results.sc3$score,
             Patient_ID = results.sc3$Patient_ID,
             joint = results.sc3$joint)
ensemble.sc3 <- ensemble.sc3[,c("Patient_ID", "joint", "weight", "score", ens_names)]
p<-lapply(ens_names, function(x){
  cor <- cor(ensemble.sc3$score, ensemble.sc3[[x]], method = 'spearman') 
  ggplot(data = ensemble.sc3) +
    geom_point(aes(x = score, y = !!sym(x))) +
    ggtitle(glue::glue("spearman = {cor}"))
})
p
[[1]]

[[2]]

[[3]]

[[4]]

[[5]]

[[6]]

[[7]]

[[8]]

[[9]]

[[10]]

[[11]]

[[12]]

[[13]]

[[14]]

bs_indices.sc3 <- matrix(1:nrow(ensemble.sc3), nrow(ensemble.sc3), N) %>%
  apply(2, sample, replace = T)
boot.sc3 <- apply(bs_indices.sc3, 2, function(ind) {
  tmp.gold <- ensemble.sc3[ind, c(1:4)]
  apply(ensemble.sc3[ind, -c(1:4)], 2, function(pred) {
    score_weighted_rmse(tmp.gold, pred)
  })
}) %>%
  t()

Bayes Factor Analysis

Use our challengescoring package to compute Bayes factors using a matrix of scores, setting the refPredIndex as the number of the column that contains the top prediction (the reference prediction).

In addition to computing BF against the top performer, we are also interested in comparing against all columns. Some tweaking to the computation will be required, as the reference index may no longer be the best, which in consequence, means the inversion of K will be dependent on which submission it is being compared with.

library(challengescoring)
computeBayesFactorWhereRefIsNotBest <- function(bootstrapMetricMatrix,
                               refPredIndex,
                               invertBayes){

    M <- as.data.frame(bootstrapMetricMatrix - bootstrapMetricMatrix[,refPredIndex])
    K <- apply(M ,2, function(x) {
      k <- sum(x >= 0)/sum(x < 0)
      if(sum(x >= 0) > sum(x < 0)){
      return(k)
      }else{
      return(1/k)
      }
    })
    if(invertBayes == T){K <- 1/K}
    K[refPredIndex] <- 0

    return(K)
}

# Top performer: Team Shirin
bayes_top.sc1 <- computeBayesFactorWhereRefIsNotBest(boot.sc1, refPredIndex=1, invertBayes=F) %>%
  as_tibble(rownames = "submission") %>%
  rename(bayes = value)

# Top performer: Hongyang Li and Yuanfang Guan (column 1)
bayes_top.sc2 <- computeBayesFactorWhereRefIsNotBest(boot.sc2, refPredIndex=1, invertBayes=F) %>%
  as_tibble(rownames = "submission") %>%
  rename(bayes = value)

# Top performer: Gold Therapy (column 1)
bayes_top.sc3 <- computeBayesFactorWhereRefIsNotBest(boot.sc3, refPredIndex=1, invertBayes=F) %>%
  as_tibble(rownames = "submission") %>%
  rename(bayes = value) 


# bayesFactorMatrix <- function(bootstrapMatrix) {
#   names <- colnames(bootstrapMatrix)
#   results <- purrr::map(1:ncol(bootstrapMatrix), function(ind) {
#     computeBayesFactorWhereRefIsNotBest(bootstrapMatrix, refPredIndex=ind, invertBayes=F) %>%
#       as.data.frame()
# }) %>% bind_cols
#   colnames(results) <- names
#   results
# }

Plot Results

Plot boxplot of all scores, coloring the boxes by Bayes factor.

plot_results <- function(results, bayes, subchallenge) {
  res <- results %>%
    as_tibble() %>%
    gather(submission, bs_score) %>%
    left_join(bayes) %>%
    mutate(bayes_category=case_when(
      bayes == 0 ~ "Reference",
      bayes<=3 ~ "<3",
      bayes>=3 & bayes <5 ~ "3-5",
      bayes>=5 & bayes <10 ~ "5-10",
      bayes>=10 ~ ">10")) 
  
  lvls <- colnames(results)
  res$submission <- factor(res$submission, levels = lvls)
  
  labs <- glue::glue("{res$submission}+")
  
  ggplot(res, aes(
      x=submission,
      y=bs_score,
      color=bayes_category
    )) +
    geom_boxplot() +
    theme_bw() +
    scale_color_manual(values = c(
      "Reference"="#d32e36", 
      '<3' = '#cf4d6f', 
      "3-5" = "#cc7e85",
      "5-10" = '#c5afa4', 
      ">10" = "#a8a6a4"),
      name = "Bayes Factor") +
    labs(x="Team", y=paste("Bootstrapped", subchallenge, "Score")) +
    theme(axis.text.x = element_text(angle = 90, hjust = 1, vjust = 0.5))
  }

Subchallenge 1

SC1 ensemble results are a little odd. Adding in RYM has a pretty substantial effect on the mean ensemble.

plot_results(boot.sc1, bayes_top.sc1, "SC1")

NA
NA

ensemble_plot_data <-ensemble.sc1 %>% 
  pivot_longer(names_to = "model", values_to = "prediction", cols = -c("weight"))

lvls <- colnames(ensemble.sc1)[-2]
ensemble_plot_data$model <- factor(ensemble_plot_data$model, levels = lvls)
  
ggplot(data = ensemble_plot_data) +
  ggbeeswarm::geom_beeswarm(aes(x = model, y = prediction), priority = "density", size = 0.1, cex = 0.4) +
      theme(axis.text.x = element_text(angle = 90, hjust = 1, vjust = 0.5))

Subchallenge 2

SC2 results look more conventional : combine top models and increase performance a bit, but effect eventually disappears.

plot_results(boot.sc2, bayes_top.sc2, "SC2")

Subchallenge 3

SC3 results look more conventional : combine top models and increase performance a bit, but effect eventually disappears.

plot_results(boot.sc3, bayes_top.sc3, "SC3")

LS0tCnRpdGxlOiAnVmFsaWRhdGlvbiByb3VuZCBlbnNlbWJsZWQgbW9kZWwgc2NvcmluZycKYXV0aG9yOiAiUm9iZXJ0IEFsbGF3YXkgKFNhZ2UgQmlvbmV0d29ya3MpIgpkYXRlOiAiYHIgU3lzLkRhdGUoKWAiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB5ZXMKICAgIGRmX3ByaW50OiBwYWdlZAogIGh0bWxfbm90ZWJvb2s6CiAgICBkZl9wcmludDogcGFnZWQKICAgIGNvZGVfZm9sZDogaGlkZQogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogeWVzCiAgcGRmX2RvY3VtZW50OgogICAgdG9jOiB5ZXMKLS0tCgoKIyMgSW50cm9kdWN0aW9uCgpPZnRlbiB0aW1lcywgYW4gZW5zZW1ibGUgb2YgbWV0aG9kcyB3aWxsIHBlcmZvcm0gYmV0dGVyIHRoYW4gdGhlIGluZGl2aWR1YWwgbWV0aG9kLiBUaGlzIGtub3duIGFzIHRoZSAid2lzZG9tIG9mIHRoZSBjcm93ZHMiIHBoZW5vbWVub24uIEFuIGVhc3kgd2F5IHRvIGdlbmVyYXRlIGFuIGVuc2VtYmxlIHByZWRpY3Rpb24gaXMgdG8gdGFrZSB0aGUgbWVhbiwgbWVkaWFuLCBvciB3ZWlnaHRlZCBhdmVyYWdlIG9mIGFsbCBvZiB0aGUgcHJlZGljdGlvbnMuIFlvdSB0aGVuIGNhbiBzY29yZSB0aGlzICJwcmVkaWN0aW9uIiBhcyB5b3Ugd291bGQgYW55IG90aGVyIHByZWRpY3Rpb24gZmlsZSB0byBhc3Nlc3MgaXQncyBwZXJmb3JtYW5jZSByZWxhdGl2ZSB0byB0aGUgc3VibWlzc2lvbnMuIAoKQW5vdGhlciBjb25zaWRlcmF0aW9uIGlzIHRoYXQgdGhlIHdpc2RvbSBvZiB0aGUgY3Jvd2RzIG1ldGhvZCBzb21ldGltZXMgYXBwbGllcyBvbmx5IHRvIGEgY2VydGFpbiBwb2ludC4gVGhhdCBpcywgaWYgeW91IG9yZGVyIGFsbCBvZiB0aGUgc3VibWl0dGVkIHByZWRpY3Rpb25zIGZyb20gaGlnaCB0byBsb3cgcGVyZm9ybWFuY2UsIHRoZXJlIG1heSBiZSBhIHBvaW50IGFmdGVyIHdoaWNoIHlvdSBubyBsb25nZXIgd2FudCB0byBhZGQgYSBwcmVkaWN0aW9uIHRvIHlvdXIgZW5zZW1ibGUgbWV0aG9kLiBBIGdvb2QgdmlzdWFsaXphdGlvbiBvZiB0aGlzIGNhbiBiZSBmb3VuZCBpbiBTdXBwbGVtZW50YWwgRmlndXJlIDggW2hlcmVdKGh0dHBzOi8vd3d3LmJpb3J4aXYub3JnL2NvbnRlbnQvMTAuMTEwMS8yMDE5LjEyLjMxLjg5MTgxMnYzLnN1cHBsZW1lbnRhcnktbWF0ZXJpYWwpLCB3aGVyZSB5b3UgY2FuIHNlZSBob3cgdGhlIGVuc2VtYmxlIHNjb3JlIGNoYW5nZXMgYWZ0ZXIgYWRkaW5nIGFkZGl0aW9uYWwgcHJlZGljdGlvbnMuIFBlcmZvcm1hbmNlIHBlYWtzIHdpdGggYW4gZW5zZW1ibGUgb2YgdGhlIHRvcCBmb3VyIHByZWRpY3Rpb25zLCBidXQgZG9lcyBub3QgaW1wcm92ZSB3aXRoIGFkZGl0aW9ucyBvZiBmdXJ0aGVyIG1vZGVscy4gCgpBIGZpbmFsIGNvbnNpZGVyYXRpb24gaGVyZSBpcyB0aGF0IGNlcnRhaW4gbW9kZWxzIG1heSBiZSBiZXR0ZXIgYXQgcHJlZGljdGluZyBjZXJ0YWluIGNvbXBvbmVudHMgb2YgdGhlIHByb2JsZW0uIFlvdSBtYXkgYmUgYWJsZSB0byBtb3JlIHN0cmF0ZWdpY2FsbHkgZW5zZW1ibGUgbWV0aG9kcyBpZiB5b3UgYXNzZXNzIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgc3VibWl0dGVkIG1vZGVscyBvbiBjYXRlZ29yaWNhbCBzdWJzZXRzIG9mIHRoZSBkYXRhIChlLmcuIGZvciBhIG1ldGhvZCBwcmVkaWN0aW5nIGFtb25nIGZvdXIgY2FuY2VyIHN1YnR5cGVzLCBzb21lIG1ldGhvZHMgbWF5IGJlIGJldHRlciBhdCBwcmVkaWN0aW5nIHN1YnR5cGUgMSB2cyB0aGUgb3RoZXIgbWV0aG9kcywgd2hpbGUgb3RoZXIgbWV0aG9kcyBtYXkgYmUgYmV0dGVyIGF0IHByZWRpY3Rpbmcgc3VidHlwZSAzIHRoYW4gb3RoZXIgbWV0aG9kcykuIFdlaWdodGluZyB0aGUgcHJlZGljdGlvbnMgZnJvbSB0aGVzZSBtZXRob2RzIHN0cmF0ZWdpY2FsbHkgbWF5IHJlc3VsdCBpbiBiZXR0ZXIgZW5zZW1ibGUgcGVyZm9ybWFuY2UuCgoKRmlyc3QsIGltcG9ydCBwYWNrYWdlcywgc2NvcmluZyBmdW5jdGlvbnMsIGFuZCBjaGFsbGVuZ2UgZGF0YS4gCgpgYGB7ciBlY2hvPVRSVUUsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHJldGljdWxhdGUpCiMgbGlicmFyeShyZWFjdGFibGUpCnVzZV9jb25kYWVudigic3luYXBzZS0yIikgI2NvbmRhIGVudmlyb25tZW50IHdpdGggc3luYXBzZSA+Mi4wIGluc3RhbGxlZApzeW5hcHNlIDwtIGltcG9ydCgnc3luYXBzZWNsaWVudCcpCnN5biA8LSBzeW5hcHNlJFN5bmFwc2UoKQoKYGBgCgpgYGB7ciBpbmNsdWRlPUZBTFNFfQojbG9naW4Kc3luJGxvZ2luKCdyYTJkcmVhbXNlcnZpY2UnLCAiIyMjIikKCmBgYAoKU2NvcmluZyBoZWxwZXIgZnVuY3Rpb25zLgoKYGBge3IgZWNobz1UUlVFLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQojIApjYWxjdWxhdGVfd2VpZ2h0IDwtIGZ1bmN0aW9uKHgpewogIHdlaWdodCA8LSBkcGx5cjo6aWZfZWxzZSh4ID09IDAsIDEsCiAgICAgICAgICAgIGRwbHlyOjppZl9lbHNlKHggPT0gMSwgMiwKICAgICAgICAgICAgZHBseXI6OmlmX2Vsc2UoeD49MiAmIHg8PTMsIDIuMTQzNTQ3LAogICAgICAgICAgICBkcGx5cjo6aWZfZWxzZSh4Pj00ICYgeDw9NywgMy44NjM3NDUsCiAgICAgICAgICAgIGRwbHlyOjppZl9lbHNlKHg+PTggJiB4PD0yMCwgOCwKICAgICAgICAgICAgZHBseXI6OmlmX2Vsc2UoeD49MjEgJiB4PD01NSwgMTYsCiAgICAgICAgICAgIGRwbHlyOjppZl9lbHNlKHg+PTU2ICYgeDw9MTQ4LCAzMiwKICAgICAgICAgICAgZHBseXI6OmlmX2Vsc2UoeD49MTQ4LCA2NCwgMCkpKSkpKSkpCiAgcmV0dXJuKHdlaWdodCkKfQoKIyAKc3VtX3dlaWdodGVkX2Vycm9yIDwtIGZ1bmN0aW9uKGdvbGQsIHByZWQsIHdlaWdodCl7CiAgc3VtKHdlaWdodCphYnMoZ29sZCAtIHByZWQpKQp9CgojIApybXNlIDwtIGZ1bmN0aW9uKGdvbGQsIHByZWQpewogIHNxcnQobWVhbigoZ29sZCAtIHByZWQpICoqIDIpKQp9CgojIFNjb3JpbmcgZnVuY3Rpb24gZm9yIGpvaW50IHdlaWdodGVkIHN1bSBSTVNFLgpzY29yZV93ZWlnaHRlZF9ybXNlIDwtIGZ1bmN0aW9uKGRmLCBwcmVkKSB7CiAgZGYkcHJlZF9zY29yZSA8LSBwcmVkCiAgZGYgJT4lIGdyb3VwX2J5KFBhdGllbnRfSUQsIHdlaWdodCkgJT4lCiAgICBzdW1tYXJpemUocGF0aWVudF9ybXNlID0gcm1zZShsb2cyKHNjb3JlKzEpLCBsb2cyKHByZWRfc2NvcmUrMSkpKSAlPiUgCiAgICB1bmdyb3VwKCkgJT4lIAogICAgc3VtbWFyaXplKHJlc3VsdD0gc3VtKHdlaWdodCpwYXRpZW50X3Jtc2UpL3N1bSh3ZWlnaHQpKSAlPiUKICAgIHBsdWNrKCJyZXN1bHQiKQp9CmBgYAoKIyMjIyBHb2xkc3RhbmRhcmQKCkZvciB0aGUgdmFsaWRhdGlvbiByb3VuZCwgd2UgaGF2ZSB0d28gZXhwZXJ0IHJlYWRlciBtZWFzdXJlbWVudHMuIFByZXZpb3VzIGFuYWx5c2lzIHNob3dlZCB0aGF0IHRoZSB2YWxpZGF0aW9uIHByZWRpY3Rpb25zIHNjb3JlZCByZWxhdGl2ZWx5IGNvbmNvcmRhbnRseSBiZXR3ZWVuIHRoZXNlIHR3byBnb2xkLXN0YW5kYXJkcywgc28gdG8gc2ltcGxpZnkgdGhpcyBhbmFseXNpcyB3ZSdsbCB0YWtlIHRoZSBhdmVyYWdlIG9mIHRoZSB0d28gZGF0YXNldHMgZm9yIGVhY2ggbWVhc3VyZW1lbnQuIAoKVGhlIGFzc2Vzc21lbnQgb2Ygc3ViY2hhbGxlbmdlIDEgdXRpbGl6aWVzIGtub3duIFN2SCBzY29yZXMgYW5kIHN1YmNoYWxsZW5nZXMgMiAmIDMga25vd24gaW5kaXZpZHVhbCBqb2ludCBuYXJyb3dpbmcgYW5kIGVyb3Npb24gc2NvcmVzLiBBZnRlciBhZGRpbmcgYSB3ZWlnaHQgZm9yIGVhY2ggam9pbnQgc2NvcmUsIHNwbGl0IHRoZSBnb2xkc3RhbmRhcmQgYWNjb3JkaW5nbHkuIAoKYGBge3IgZWNobz1UUlVFLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpnb2xkXzEgPC0gc3luJGdldCgic3luMjUzMjQyNjMiKSRwYXRoICU+JSByZWFkX2NzdigpCgpnb2xkXzIgPC0gc3luJGdldCgic3luMjUzMjQyNjIiKSRwYXRoICU+JSByZWFkX2NzdigpCgpnb2xkIDwtIGJpbmRfcm93cyhnb2xkXzEsIGdvbGRfMikgJT4lIAogIGdyb3VwX2J5KFBhdGllbnRfSUQpICU+JSAKICBzdW1tYXJpemUoYWNyb3NzKC5mbnMgPSBtZWFuKSkgJT4lIAogIG11dGF0ZSh3ZWlnaHQgPSBjYWxjdWxhdGVfd2VpZ2h0KE92ZXJhbGxfVG9sKSkKCmdvbGQuc2MxIDwtIGdvbGQgJT4lIAogIHNlbGVjdChQYXRpZW50X0lELCBPdmVyYWxsX1RvbCwgd2VpZ2h0KQoKZ29sZF9qb2ludHMgPC0gZ29sZCAlPiUKICBzZWxlY3QoLU92ZXJhbGxfVG9sKSAlPiUKICBnYXRoZXIoJ2pvaW50JywgJ3Njb3JlJywgLVBhdGllbnRfSUQsIC13ZWlnaHQpCmBgYAoKLS0tCgojIyBCb290c3RyYXAgU3VibWlzc2lvbnMKClJlYWQgaW4gcHJlZGljdGlvbiBmaWxlcywgY29tYmluZSwgdGhlbiBib290c3RyYXAgdGhlIHByZWRpY3Rpb25zICsgYSBnb2xkIHN0YW5kYXJkIDEwMDAgdGltZXMgdG8gY2FsY3VsYXRlIDEwMDAgc2NvcmVzIHBlciBwcmVkaWN0aW9uLiAKCmBgYHtyIGVjaG89VFJVRSwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KTiA8LSAxMDAwICAjIG51bWJlciBvZiBib290c3RyYXBwZWQgc2NvcmVzIHRvIGJlIGNhbGN1bGF0ZWQKCnF1ZXJ5IDwtIHN5biR0YWJsZVF1ZXJ5KAogICJTRUxFQ1QgaWQsIHByZWRpY3Rpb25fZmlsZWlkLCBvcmlnaW5hbF9zdWJtaXR0ZXJpZCBhcyBzdWJtaXR0ZXJpZCwgY3JlYXRlZE9uLAogICAgc2MxX3dlaWdodGVkX3N1bV9lcnJvciBBUyBzYzEsIAogICAgc2MyX2pvaW50X3dlaWdodGVkX3N1bV9ybXNlIEFTIHNjMiwgCiAgICBzYzNfam9pbnRfd2VpZ2h0ZWRfc3VtX3Jtc2UgQVMgc2MzCiAgRlJPTSBzeW4yNTE4NjEyMyBXSEVSRSBzdGF0dXMgPSAnQUNDRVBURUQnIikkYXNEYXRhRnJhbWUoKSAlPiUKICBncm91cF9ieShzdWJtaXR0ZXJpZCkgJT4lCiAgc2xpY2Uod2hpY2gubWF4KGNyZWF0ZWRPbikpICU+JQogIHNlbGVjdCgtY3JlYXRlZE9uKQoKIyBGb3IgZWFzaWVyIGlkZW50aWZpY2F0aW9uLCByZXBsYWNlIGVhY2ggdGVhbS9wYXJ0aWNpcGFudCdzIHN1Ym1pdHRlcmlkIHdpdGgKIyB0aGVpciB0ZWFtIG5hbWUvdXNlcm5hbWUuCnF1ZXJ5JHN1Ym1pdHRlcmlkIDwtIGFzLmNoYXJhY3RlcihxdWVyeSRzdWJtaXR0ZXJpZCkKdGVhbV9uYW1lcyA8LSBzYXBwbHkocXVlcnkkc3VibWl0dGVyaWQsIGZ1bmN0aW9uKHN1YikgewogIG5hbWUgPC0gdHJ5Q2F0Y2goewogICAgc3luJGdldFVzZXJQcm9maWxlKHN1YikkdXNlck5hbWUKICB9LCBlcnJvciA9IGZ1bmN0aW9uKGVycikgewogICAgc3luJGdldFRlYW0oc3ViKSRuYW1lCiAgfSkKICByZXR1cm4obmFtZSkKfSkKcXVlcnkkc3VibWl0dGVyaWQgPC0gdGVhbV9uYW1lcwoKcHJlZF9maWxlbmFtZXMgPC0gbGFwcGx5KHF1ZXJ5JHByZWRpY3Rpb25fZmlsZWlkLCBmdW5jdGlvbihpZCkgewogIHN5biRnZXQoaWQpJHBhdGgKfSkKbmFtZXMocHJlZF9maWxlbmFtZXMpIDwtIHRlYW1fbmFtZXMKCiMgQmVmb3JlIGJvb3RzdHJhcHBpbmcsIHJlYXJyYW5nZSB0aGUgdGVhbXMgYnkgcmFuaywgd2hlcmUgbGVmdCA9IGJldHRlciAKIyBwZXJmb3JtYW5jZSBhbmQgcmlnaHQgPSBub3QtYXMtZ3JlYXQgcGVyZm9ybWFuY2UuCgojIyMgU0MxCnN1Ym1pc3Npb25zLnNjMSA8LSBsYXBwbHkobmFtZXMocHJlZF9maWxlbmFtZXMpLCBmdW5jdGlvbih0ZWFtKSB7CiAgcmVhZC5jc3YocHJlZF9maWxlbmFtZXNbW3RlYW1dXSkgJT4lIAogICAgbXV0YXRlX2F0KHZhcnMoLVBhdGllbnRfSUQpLCB+IHJlcGxhY2UoLiwgd2hpY2goLjwwKSwgMCkpICU+JQogICAgc2VsZWN0KFBhdGllbnRfSUQsIE92ZXJhbGxfVG9sKSAlPiUKICAgIHJlbmFtZSghIXRlYW0gOj0gT3ZlcmFsbF9Ub2wpCn0pICU+JQogIHJlZHVjZShsZWZ0X2pvaW4sIGJ5PSJQYXRpZW50X0lEIikgJT4lCiAgbGVmdF9qb2luKGdvbGQuc2MxLCBieT0iUGF0aWVudF9JRCIpICU+JQogIHJlbmFtZShnb2xkID0gT3ZlcmFsbF9Ub2wpCgpyZXN1bHRzLnNjMSA8LSBzdWJtaXNzaW9ucy5zYzFbLGMoImdvbGQiLCAid2VpZ2h0IiwgKHF1ZXJ5ICU+JSBhcnJhbmdlKHNjMSkpJHN1Ym1pdHRlcmlkKV0KCmVuc2VtYmxlLnNjMSA8LSBzYXBwbHkoMzpuY29sKHJlc3VsdHMuc2MxKSwgZnVuY3Rpb24oeCl7CiAgbmV3X2NvbCA8LSByZXN1bHRzLnNjMSAlPiUgCiAgICBzZWxlY3QoMzp4KSAlPiUgCiAgICByb3dNZWFucygpCn0pICU+JSAKICBhcy5kYXRhLmZyYW1lKCkKCmVuc19uYW1lcyA8LSBjKGdsdWU6OmdsdWUoIntjb2xuYW1lcyhyZXN1bHRzLnNjMSlbM119IiksIGdsdWU6OmdsdWUoIit7Y29sbmFtZXMocmVzdWx0cy5zYzEpWy0xOi0zXX0iKSkKY29sbmFtZXMoZW5zZW1ibGUuc2MxKSA8LSBlbnNfbmFtZXMKCmVuc2VtYmxlLnNjMSA8LSBlbnNlbWJsZS5zYzEgJT4lIAogIGFkZF9jb2x1bW4od2VpZ2h0ID0gcmVzdWx0cy5zYzEkd2VpZ2h0KSAlPiUgCiAgYWRkX2NvbHVtbihnb2xkID0gcmVzdWx0cy5zYzEkZ29sZCkKCmVuc2VtYmxlLnNjMSA8LSBlbnNlbWJsZS5zYzFbLGMoImdvbGQiLCAid2VpZ2h0IiwgZW5zX25hbWVzKV0KCnA8LWxhcHBseShlbnNfbmFtZXMsIGZ1bmN0aW9uKHgpewogIGNvciA8LSBjb3IoZW5zZW1ibGUuc2MxJGdvbGQsIGVuc2VtYmxlLnNjMVtbeF1dLCBtZXRob2QgPSAnc3BlYXJtYW4nKQogIGdncGxvdChkYXRhID0gZW5zZW1ibGUuc2MxKSArCiAgICBnZW9tX3BvaW50KGFlcyh4ID0gZ29sZCwgeSA9ICEhc3ltKHgpKSkgKwogICAgZ2d0aXRsZShnbHVlOjpnbHVlKCJzcGVhcm1hbiA9IHtjb3J9IikpCn0pCgpic19pbmRpY2VzLnNjMSA8LSBtYXRyaXgoMTpucm93KGVuc2VtYmxlLnNjMSksIG5yb3coZW5zZW1ibGUuc2MxKSwgTikgJT4lCiAgYXBwbHkoMiwgc2FtcGxlLCByZXBsYWNlID0gVCkKCmJvb3Quc2MxIDwtIGFwcGx5KGJzX2luZGljZXMuc2MxLCAyLCBmdW5jdGlvbihpbmQpIHsKICB0bXAuZ29sZCA8LSBlbnNlbWJsZS5zYzFbaW5kLGMoMToyKV0KICBhcHBseShlbnNlbWJsZS5zYzFbaW5kLCAtYygxOjIpXSwgMiwgZnVuY3Rpb24ocHJlZCkgewogICAgc3VtX3dlaWdodGVkX2Vycm9yKAogICAgICBsb2cyKHRtcC5nb2xkJGdvbGQgKyAxKSwKICAgICAgbG9nMihwcmVkICsgMSksCiAgICAgIHRtcC5nb2xkJHdlaWdodAogICAgKSAvIHN1bSh0bXAuZ29sZCR3ZWlnaHQpCiAgfSkKfSkgJT4lCiAgdCgpCgoKCgojIyMgU0MyCnN1Ym1pc3Npb25zLnNjMiA8LSBsYXBwbHkobmFtZXMocHJlZF9maWxlbmFtZXMpLCBmdW5jdGlvbih0ZWFtKSB7CiAgcmVhZC5jc3YocHJlZF9maWxlbmFtZXNbW3RlYW1dXSkgJT4lIAogICAgc2VsZWN0KC1PdmVyYWxsX1RvbCkgJT4lCiAgICBnYXRoZXIoJ2pvaW50JywgISF0ZWFtLCAtUGF0aWVudF9JRCkKfSkgJT4lCiAgcmVkdWNlKGxlZnRfam9pbiwgYnk9YygiUGF0aWVudF9JRCIsICJqb2ludCIpKSAlPiUKICBsZWZ0X2pvaW4oZ29sZF9qb2ludHMsIGJ5PWMoIlBhdGllbnRfSUQiLCAiam9pbnQiKSkKCnJlc3VsdHMuc2MyIDwtIHN1Ym1pc3Npb25zLnNjMlssIGMoCiAgICAiUGF0aWVudF9JRCIsICJqb2ludCIsICJ3ZWlnaHQiLCAic2NvcmUiLCAocXVlcnkgJT4lIGFycmFuZ2Uoc2MyKSkkc3VibWl0dGVyaWQKICApXSAlPiUKICBmaWx0ZXIoZ3JlcGwoIi4rX0pfXy4rIiwgam9pbnQpKQoKZW5zZW1ibGUuc2MyIDwtIHNhcHBseSg1Om5jb2wocmVzdWx0cy5zYzIpLCBmdW5jdGlvbih4KXsKICBuZXdfY29sIDwtIHJlc3VsdHMuc2MyICU+JSAKICAgIHNlbGVjdCg1OngpICU+JSAKICAgIG11dGF0ZSghIXN5bShhcy5jaGFyYWN0ZXIoeCkpIDo9IHJvd01lYW5zKGFjcm9zcyh3aGVyZShpcy5udW1lcmljKSkpKSAlPiUgCiAgICBwbHVjayhhcy5jaGFyYWN0ZXIoeCkpCn0pICU+JSAKICBhcy5kYXRhLmZyYW1lKCkKCmVuc19uYW1lcyA8LSBjKGdsdWU6OmdsdWUoIntjb2xuYW1lcyhyZXN1bHRzLnNjMilbNV19IiksIGdsdWU6OmdsdWUoIit7Y29sbmFtZXMocmVzdWx0cy5zYzIpWy0xOi01XX0iKSkKY29sbmFtZXMoZW5zZW1ibGUuc2MyKSA8LSBlbnNfbmFtZXMKCmVuc2VtYmxlLnNjMiA8LSBlbnNlbWJsZS5zYzIgJT4lIAogIGFkZF9jb2x1bW4od2VpZ2h0ID0gcmVzdWx0cy5zYzIkd2VpZ2h0LAogICAgICAgICAgICAgc2NvcmUgPSByZXN1bHRzLnNjMiRzY29yZSwKICAgICAgICAgICAgIFBhdGllbnRfSUQgPSByZXN1bHRzLnNjMiRQYXRpZW50X0lELAogICAgICAgICAgICAgam9pbnQgPSByZXN1bHRzLnNjMiRqb2ludCkKCmVuc2VtYmxlLnNjMiA8LSBlbnNlbWJsZS5zYzJbLGMoIlBhdGllbnRfSUQiLCAiam9pbnQiLCAid2VpZ2h0IiwgInNjb3JlIiwgZW5zX25hbWVzKV0KCnA8LWxhcHBseShlbnNfbmFtZXMsIGZ1bmN0aW9uKHgpewogIGNvciA8LSBjb3IoZW5zZW1ibGUuc2MyJHNjb3JlLCBlbnNlbWJsZS5zYzJbW3hdXSwgbWV0aG9kID0gJ3NwZWFybWFuJykgCiAgZ2dwbG90KGRhdGEgPSBlbnNlbWJsZS5zYzIpICsKICAgIGdlb21fcG9pbnQoYWVzKHggPSBzY29yZSwgeSA9ICEhc3ltKHgpKSkgKwogICAgZ2d0aXRsZShnbHVlOjpnbHVlKCJzcGVhcm1hbiA9IHtjb3J9IikpCn0pCgpwCgpic19pbmRpY2VzLnNjMiA8LSBtYXRyaXgoMTpucm93KGVuc2VtYmxlLnNjMiksIG5yb3coZW5zZW1ibGUuc2MyKSwgTikgJT4lCiAgYXBwbHkoMiwgc2FtcGxlLCByZXBsYWNlID0gVCkKCmJvb3Quc2MyIDwtIGFwcGx5KGJzX2luZGljZXMuc2MyLCAyLCBmdW5jdGlvbihpbmQpIHsKICB0bXAuZ29sZCA8LSBlbnNlbWJsZS5zYzJbaW5kLCBjKDE6NCldCiAgYXBwbHkoZW5zZW1ibGUuc2MyW2luZCwgLWMoMTo0KV0sIDIsIGZ1bmN0aW9uKHByZWQpIHsKICAgIHNjb3JlX3dlaWdodGVkX3Jtc2UodG1wLmdvbGQsIHByZWQpCiAgfSkKfSkgJT4lCiAgdCgpCgojIyMgU0MzCnN1Ym1pc3Npb25zLnNjMyA8LSBsYXBwbHkobmFtZXMocHJlZF9maWxlbmFtZXMpLCBmdW5jdGlvbih0ZWFtKSB7CiAgcmVhZC5jc3YocHJlZF9maWxlbmFtZXNbW3RlYW1dXSkgJT4lIAogICAgc2VsZWN0KC1PdmVyYWxsX1RvbCkgJT4lCiAgICBnYXRoZXIoJ2pvaW50JywgISF0ZWFtLCAtUGF0aWVudF9JRCkKfSkgJT4lCiAgcmVkdWNlKGxlZnRfam9pbiwgYnk9YygiUGF0aWVudF9JRCIsICJqb2ludCIpKSAlPiUKICBsZWZ0X2pvaW4oZ29sZF9qb2ludHMsIGJ5PWMoIlBhdGllbnRfSUQiLCAiam9pbnQiKSkKCnJlc3VsdHMuc2MzIDwtIHN1Ym1pc3Npb25zLnNjM1ssIGMoCiAgICAiUGF0aWVudF9JRCIsICJqb2ludCIsICJ3ZWlnaHQiLCAic2NvcmUiLCAocXVlcnkgJT4lIGFycmFuZ2Uoc2MzKSkkc3VibWl0dGVyaWQKICApXSAlPiUKICBmaWx0ZXIoZ3JlcGwoIi4rX0VfXy4rIiwgam9pbnQpKQoKZW5zZW1ibGUuc2MzIDwtIHNhcHBseSg1Om5jb2wocmVzdWx0cy5zYzMpLCBmdW5jdGlvbih4KXsKICBuZXdfY29sIDwtIHJlc3VsdHMuc2MzICU+JSAKICAgIHNlbGVjdCg1OngpICU+JSAKICAgIG11dGF0ZSghIXN5bShhcy5jaGFyYWN0ZXIoeCkpIDo9IHJvd01lYW5zKGFjcm9zcyh3aGVyZShpcy5udW1lcmljKSkpKSAlPiUgCiAgICBwbHVjayhhcy5jaGFyYWN0ZXIoeCkpCn0pICU+JSAKICBhcy5kYXRhLmZyYW1lKCkKCmVuc19uYW1lcyA8LSBjKGdsdWU6OmdsdWUoIntjb2xuYW1lcyhyZXN1bHRzLnNjMylbNV19IiksIGdsdWU6OmdsdWUoIit7Y29sbmFtZXMocmVzdWx0cy5zYzMpWy0xOi01XX0iKSkKY29sbmFtZXMoZW5zZW1ibGUuc2MzKSA8LSBlbnNfbmFtZXMKCmVuc2VtYmxlLnNjMyA8LSBlbnNlbWJsZS5zYzMgJT4lIAogIGFkZF9jb2x1bW4od2VpZ2h0ID0gcmVzdWx0cy5zYzMkd2VpZ2h0LAogICAgICAgICAgICAgc2NvcmUgPSByZXN1bHRzLnNjMyRzY29yZSwKICAgICAgICAgICAgIFBhdGllbnRfSUQgPSByZXN1bHRzLnNjMyRQYXRpZW50X0lELAogICAgICAgICAgICAgam9pbnQgPSByZXN1bHRzLnNjMyRqb2ludCkKCmVuc2VtYmxlLnNjMyA8LSBlbnNlbWJsZS5zYzNbLGMoIlBhdGllbnRfSUQiLCAiam9pbnQiLCAid2VpZ2h0IiwgInNjb3JlIiwgZW5zX25hbWVzKV0KCnA8LWxhcHBseShlbnNfbmFtZXMsIGZ1bmN0aW9uKHgpewogIGNvciA8LSBjb3IoZW5zZW1ibGUuc2MzJHNjb3JlLCBlbnNlbWJsZS5zYzNbW3hdXSwgbWV0aG9kID0gJ3NwZWFybWFuJykgCiAgZ2dwbG90KGRhdGEgPSBlbnNlbWJsZS5zYzMpICsKICAgIGdlb21fcG9pbnQoYWVzKHggPSBzY29yZSwgeSA9ICEhc3ltKHgpKSkgKwogICAgZ2d0aXRsZShnbHVlOjpnbHVlKCJzcGVhcm1hbiA9IHtjb3J9IikpCn0pCgpwCgpic19pbmRpY2VzLnNjMyA8LSBtYXRyaXgoMTpucm93KGVuc2VtYmxlLnNjMyksIG5yb3coZW5zZW1ibGUuc2MzKSwgTikgJT4lCiAgYXBwbHkoMiwgc2FtcGxlLCByZXBsYWNlID0gVCkKCmJvb3Quc2MzIDwtIGFwcGx5KGJzX2luZGljZXMuc2MzLCAyLCBmdW5jdGlvbihpbmQpIHsKICB0bXAuZ29sZCA8LSBlbnNlbWJsZS5zYzNbaW5kLCBjKDE6NCldCiAgYXBwbHkoZW5zZW1ibGUuc2MzW2luZCwgLWMoMTo0KV0sIDIsIGZ1bmN0aW9uKHByZWQpIHsKICAgIHNjb3JlX3dlaWdodGVkX3Jtc2UodG1wLmdvbGQsIHByZWQpCiAgfSkKfSkgJT4lCiAgdCgpCmBgYAoKLS0tCgojIyBCYXllcyBGYWN0b3IgQW5hbHlzaXMKClVzZSBvdXIgYGNoYWxsZW5nZXNjb3JpbmdgIHBhY2thZ2UgdG8gY29tcHV0ZSBCYXllcyBmYWN0b3JzIHVzaW5nIGEgbWF0cml4IG9mIHNjb3Jlcywgc2V0dGluZyB0aGUgYHJlZlByZWRJbmRleGAgYXMgdGhlIG51bWJlciBvZiB0aGUgY29sdW1uIHRoYXQgY29udGFpbnMgdGhlIHRvcCBwcmVkaWN0aW9uICh0aGUgcmVmZXJlbmNlIHByZWRpY3Rpb24pLgoKSW4gYWRkaXRpb24gdG8gY29tcHV0aW5nIEJGIGFnYWluc3QgdGhlIHRvcCBwZXJmb3JtZXIsIHdlIGFyZSBhbHNvIGludGVyZXN0ZWQgaW4gY29tcGFyaW5nIGFnYWluc3QgYWxsIGNvbHVtbnMuIFNvbWUgdHdlYWtpbmcgdG8gdGhlIGNvbXB1dGF0aW9uIHdpbGwgYmUgcmVxdWlyZWQsIGFzIHRoZSByZWZlcmVuY2UgaW5kZXggbWF5IG5vIGxvbmdlciBiZSB0aGUgYmVzdCwgd2hpY2ggaW4gY29uc2VxdWVuY2UsIG1lYW5zIHRoZSBpbnZlcnNpb24gb2YgSyB3aWxsIGJlIGRlcGVuZGVudCBvbiB3aGljaCBzdWJtaXNzaW9uIGl0IGlzIGJlaW5nIGNvbXBhcmVkIHdpdGguCgpgYGB7ciBlY2hvPVRSVUUsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY2hhbGxlbmdlc2NvcmluZykKY29tcHV0ZUJheWVzRmFjdG9yV2hlcmVSZWZJc05vdEJlc3QgPC0gZnVuY3Rpb24oYm9vdHN0cmFwTWV0cmljTWF0cml4LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVmUHJlZEluZGV4LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW52ZXJ0QmF5ZXMpewoKICAgIE0gPC0gYXMuZGF0YS5mcmFtZShib290c3RyYXBNZXRyaWNNYXRyaXggLSBib290c3RyYXBNZXRyaWNNYXRyaXhbLHJlZlByZWRJbmRleF0pCiAgICBLIDwtIGFwcGx5KE0gLDIsIGZ1bmN0aW9uKHgpIHsKICAgICAgayA8LSBzdW0oeCA+PSAwKS9zdW0oeCA8IDApCiAgICAgIGlmKHN1bSh4ID49IDApID4gc3VtKHggPCAwKSl7CiAgICAgIHJldHVybihrKQogICAgICB9ZWxzZXsKICAgICAgcmV0dXJuKDEvaykKICAgICAgfQogICAgfSkKICAgIGlmKGludmVydEJheWVzID09IFQpe0sgPC0gMS9LfQogICAgS1tyZWZQcmVkSW5kZXhdIDwtIDAKCiAgICByZXR1cm4oSykKfQoKIyBUb3AgcGVyZm9ybWVyOiBUZWFtIFNoaXJpbgpiYXllc190b3Auc2MxIDwtIGNvbXB1dGVCYXllc0ZhY3RvcldoZXJlUmVmSXNOb3RCZXN0KGJvb3Quc2MxLCByZWZQcmVkSW5kZXg9MSwgaW52ZXJ0QmF5ZXM9RikgJT4lCiAgYXNfdGliYmxlKHJvd25hbWVzID0gInN1Ym1pc3Npb24iKSAlPiUKICByZW5hbWUoYmF5ZXMgPSB2YWx1ZSkKCiMgVG9wIHBlcmZvcm1lcjogSG9uZ3lhbmcgTGkgYW5kIFl1YW5mYW5nIEd1YW4gKGNvbHVtbiAxKQpiYXllc190b3Auc2MyIDwtIGNvbXB1dGVCYXllc0ZhY3RvcldoZXJlUmVmSXNOb3RCZXN0KGJvb3Quc2MyLCByZWZQcmVkSW5kZXg9MSwgaW52ZXJ0QmF5ZXM9RikgJT4lCiAgYXNfdGliYmxlKHJvd25hbWVzID0gInN1Ym1pc3Npb24iKSAlPiUKICByZW5hbWUoYmF5ZXMgPSB2YWx1ZSkKCiMgVG9wIHBlcmZvcm1lcjogR29sZCBUaGVyYXB5IChjb2x1bW4gMSkKYmF5ZXNfdG9wLnNjMyA8LSBjb21wdXRlQmF5ZXNGYWN0b3JXaGVyZVJlZklzTm90QmVzdChib290LnNjMywgcmVmUHJlZEluZGV4PTEsIGludmVydEJheWVzPUYpICU+JQogIGFzX3RpYmJsZShyb3duYW1lcyA9ICJzdWJtaXNzaW9uIikgJT4lCiAgcmVuYW1lKGJheWVzID0gdmFsdWUpIAoKCiMgYmF5ZXNGYWN0b3JNYXRyaXggPC0gZnVuY3Rpb24oYm9vdHN0cmFwTWF0cml4KSB7CiMgICBuYW1lcyA8LSBjb2xuYW1lcyhib290c3RyYXBNYXRyaXgpCiMgICByZXN1bHRzIDwtIHB1cnJyOjptYXAoMTpuY29sKGJvb3RzdHJhcE1hdHJpeCksIGZ1bmN0aW9uKGluZCkgewojICAgICBjb21wdXRlQmF5ZXNGYWN0b3JXaGVyZVJlZklzTm90QmVzdChib290c3RyYXBNYXRyaXgsIHJlZlByZWRJbmRleD1pbmQsIGludmVydEJheWVzPUYpICU+JQojICAgICAgIGFzLmRhdGEuZnJhbWUoKQojIH0pICU+JSBiaW5kX2NvbHMKIyAgIGNvbG5hbWVzKHJlc3VsdHMpIDwtIG5hbWVzCiMgICByZXN1bHRzCiMgfQpgYGAKCi0tLQoKIyMgUGxvdCBSZXN1bHRzCgpQbG90IGJveHBsb3Qgb2YgYWxsIHNjb3JlcywgY29sb3JpbmcgdGhlIGJveGVzIGJ5IEJheWVzIGZhY3Rvci4gCgpgYGB7ciBlY2hvPVRSVUUsIG1lc3NhZ2U9RkFMU0V9CnBsb3RfcmVzdWx0cyA8LSBmdW5jdGlvbihyZXN1bHRzLCBiYXllcywgc3ViY2hhbGxlbmdlKSB7CiAgcmVzIDwtIHJlc3VsdHMgJT4lCiAgICBhc190aWJibGUoKSAlPiUKICAgIGdhdGhlcihzdWJtaXNzaW9uLCBic19zY29yZSkgJT4lCiAgICBsZWZ0X2pvaW4oYmF5ZXMpICU+JQogICAgbXV0YXRlKGJheWVzX2NhdGVnb3J5PWNhc2Vfd2hlbigKICAgICAgYmF5ZXMgPT0gMCB+ICJSZWZlcmVuY2UiLAogICAgICBiYXllczw9MyB+ICI8MyIsCiAgICAgIGJheWVzPj0zICYgYmF5ZXMgPDUgfiAiMy01IiwKICAgICAgYmF5ZXM+PTUgJiBiYXllcyA8MTAgfiAiNS0xMCIsCiAgICAgIGJheWVzPj0xMCB+ICI+MTAiKSkgCiAgCiAgbHZscyA8LSBjb2xuYW1lcyhyZXN1bHRzKQogIHJlcyRzdWJtaXNzaW9uIDwtIGZhY3RvcihyZXMkc3VibWlzc2lvbiwgbGV2ZWxzID0gbHZscykKICAKICBsYWJzIDwtIGdsdWU6OmdsdWUoIntyZXMkc3VibWlzc2lvbn0rIikKICAKICBnZ3Bsb3QocmVzLCBhZXMoCiAgICAgIHg9c3VibWlzc2lvbiwKICAgICAgeT1ic19zY29yZSwKICAgICAgY29sb3I9YmF5ZXNfY2F0ZWdvcnkKICAgICkpICsKICAgIGdlb21fYm94cGxvdCgpICsKICAgIHRoZW1lX2J3KCkgKwogICAgc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGMoCiAgICAgICJSZWZlcmVuY2UiPSIjZDMyZTM2IiwgCiAgICAgICc8MycgPSAnI2NmNGQ2ZicsIAogICAgICAiMy01IiA9ICIjY2M3ZTg1IiwKICAgICAgIjUtMTAiID0gJyNjNWFmYTQnLCAKICAgICAgIj4xMCIgPSAiI2E4YTZhNCIpLAogICAgICBuYW1lID0gIkJheWVzIEZhY3RvciIpICsKICAgIGxhYnMoeD0iVGVhbSIsIHk9cGFzdGUoIkJvb3RzdHJhcHBlZCIsIHN1YmNoYWxsZW5nZSwgIlNjb3JlIikpICsKICAgIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIGhqdXN0ID0gMSwgdmp1c3QgPSAwLjUpKQogIH0KYGBgCgojIyMgU3ViY2hhbGxlbmdlIDEKClNDMSBlbnNlbWJsZSByZXN1bHRzIGFyZSBhIGxpdHRsZSBvZGQuIEFkZGluZyBpbiBSWU0gaGFzIGEgcHJldHR5IHN1YnN0YW50aWFsIGVmZmVjdCBvbiB0aGUgbWVhbiBlbnNlbWJsZS4gCgpgYGB7ciBlY2hvPVRSVUUsIG1lc3NhZ2U9RkFMU0V9CnBsb3RfcmVzdWx0cyhib290LnNjMSwgYmF5ZXNfdG9wLnNjMSwgIlNDMSIpCmBgYAoKYGBge3IgZWNobz1UUlVFLCBtZXNzYWdlPUZBTFNFfQoKZW5zZW1ibGVfcGxvdF9kYXRhIDwtZW5zZW1ibGUuc2MxICU+JSAKICBwaXZvdF9sb25nZXIobmFtZXNfdG8gPSAibW9kZWwiLCB2YWx1ZXNfdG8gPSAicHJlZGljdGlvbiIsIGNvbHMgPSAtYygid2VpZ2h0IikpCgpsdmxzIDwtIGNvbG5hbWVzKGVuc2VtYmxlLnNjMSlbLTJdCmVuc2VtYmxlX3Bsb3RfZGF0YSRtb2RlbCA8LSBmYWN0b3IoZW5zZW1ibGVfcGxvdF9kYXRhJG1vZGVsLCBsZXZlbHMgPSBsdmxzKQogIApnZ3Bsb3QoZGF0YSA9IGVuc2VtYmxlX3Bsb3RfZGF0YSkgKwogIGdnYmVlc3dhcm06Omdlb21fYmVlc3dhcm0oYWVzKHggPSBtb2RlbCwgeSA9IHByZWRpY3Rpb24pLCBwcmlvcml0eSA9ICJkZW5zaXR5Iiwgc2l6ZSA9IDAuMSwgY2V4ID0gMC40KSArCiAgICAgIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIGhqdXN0ID0gMSwgdmp1c3QgPSAwLjUpKQoKYGBgCgojIyMgU3ViY2hhbGxlbmdlIDIKClNDMiByZXN1bHRzIGxvb2sgbW9yZSBjb252ZW50aW9uYWwgOiBjb21iaW5lIHRvcCBtb2RlbHMgYW5kIGluY3JlYXNlIHBlcmZvcm1hbmNlIGEgYml0LCBidXQgZWZmZWN0IGV2ZW50dWFsbHkgZGlzYXBwZWFycy4gCgpgYGB7ciBlY2hvPVRSVUUsIG1lc3NhZ2U9RkFMU0V9CnBsb3RfcmVzdWx0cyhib290LnNjMiwgYmF5ZXNfdG9wLnNjMiwgIlNDMiIpCmBgYAoKIyMjIFN1YmNoYWxsZW5nZSAzCgpTQzMgcmVzdWx0cyBsb29rIG1vcmUgY29udmVudGlvbmFsIDogY29tYmluZSB0b3AgbW9kZWxzIGFuZCBpbmNyZWFzZSBwZXJmb3JtYW5jZSBhIGJpdCwgYnV0IGVmZmVjdCBldmVudHVhbGx5IGRpc2FwcGVhcnMuIAoKYGBge3IgZWNobz1UUlVFLCBtZXNzYWdlPUZBTFNFfQpwbG90X3Jlc3VsdHMoYm9vdC5zYzMsIGJheWVzX3RvcC5zYzMsICJTQzMiKQpgYGAK